package LeetCode刷题.之前的算法;

public class maxArray {
    //求最大子数组的和
    public static void main(String arg[]){
        int nums[]={-2,1,-3,4,-1,2,1,-5,};
        System.out.println(maxSubArray(nums));
    }
    public static int maxSubArray(int[] nums) {
        int ans=nums[0];
        for(int i=1;i<nums.length;i++){
            //运用了动态规划的思想，且因为直接将nums数组作为dp数组，所以空间复杂度为O(1)
            nums[i]+=Math.max(nums[i-1],0);//判断其前一个值是否会对最终的答案最大组数组的和做出负影响
            ans=Math.max(nums[i],ans);//如果影响为负的，则不加
        }
        return ans;
    }
}
